CODE 28. Construct Binary Tree from Preorder and Inorder Traversal

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/09/20/2013-09-20-CODE 28 Construct Binary Tree from Preorder and Inorder Traversal/

访问原文「CODE 28. Construct Binary Tree from Preorder and Inorder Traversal」

Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.

public TreeNode buildTree(int[] preorder, int[] inorder) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (null == inorder || null == preorder || inorder.length <= 0
			|| preorder.length <= 0) {
		return null;
	}
	return dfs(inorder, preorder, 0, inorder.length - 1, 0,
			preorder.length - 1);
}

TreeNode dfs(int[] inorder, int[] preorder, int inorderStart,
		int inorderEnd, int preorderStart, int preorderEnd) {
	TreeNode node = new TreeNode(preorder[preorderStart]);
	int nodeIndexInInorder = findElement(inorder, preorder[preorderStart]);
	int leftLength = nodeIndexInInorder - inorderStart;
	int rightLength = inorderEnd - nodeIndexInInorder;
	if (leftLength > 0) {
		TreeNode left = dfs(inorder, preorder, inorderStart,
				nodeIndexInInorder - 1, preorderStart + 1, preorderStart
						+ leftLength);
		node.left = left;
	}
	if (rightLength > 0) {
		TreeNode right = dfs(inorder, preorder, nodeIndexInInorder + 1,
				inorderEnd, preorderEnd - rightLength + 1, preorderEnd);
		node.right = right;
	}
	return node;
}

int findElement(int[] array, int element) {
	for (int i = 0; i < array.length; i++) {
		if (array[i] == element) {
			return i;
		}
	}
	return -1;
}